1. Technical Field
The present invention relates to an encryption technique as an information security technique, and particularly to the generation of parameters for an NTRU (a trademark of NTRU cryptosystems, Inc.) cryptosystem.
2. Description of the Related Art
Encrypted communication using public key encryption is one of the methods to realize confidential communications between a transmission apparatus and a receiving apparatus. In a public key cryptosystem, the transmission apparatus encrypts the contents of a communication using a public key of the receiving apparatus and transmits it to the receiving apparatus, and the receiving apparatus then receives the encrypted contents and obtains the original contents by decrypting it with its own private key (e.g. See Document 1: Modern Cryptography. Mathematics in Information Science. Ser. Tatsuaki Okamoto, and Hirosuke Yamamoto, Sangyo Tosho, 1997). In the general encryption system using this method, plural transmission apparatuses and receiving apparatuses exist. A transmission apparatus firstly acquires a public key of the destination receiving apparatus. This public key makes a pair with the private key possessed by the destination receiving apparatus and is made public in the encryption system. Then, the transmission apparatus encrypts and transmits the data to be communicated using the public key obtained as above, whereas the receiving apparatus receives such encrypted communication data, decrypts the data using its own private key, and obtains the original data.
Note that encryption, which aims at realizing confidential communications between a transmission apparatus and a receiving apparatus, is of course required to ensure security against decryption performed by third parties. In a public key cryptosystem, the following two types of decryption are possible: communication data (hereinafter referred to as “plain text”) is decrypted based on encrypted communication data (hereinafter referred to as “encrypted text”); and a private key, which is privately possessed by a receiving apparatus to obtain a plain text from an encrypted text, is decrypted. In general, it is required in public key encryption that it takes a sufficiently long time for third parties to perform such decryption (e.g., it takes 1000 years by use of the latest computer), i.e., such decryption cannot be performed within a realistic time period.
In 1996, an NTRU cryptosystem was proposed as a public key encryption system capable of high-speed processing (e.g. See Document 2: Jeffery Hoffstein, Jill Pipher, and Joseph H. Silverman, “NTRU: A ring based public key cryptosystem”, Lecture Notes in Computer Science, 1423, pp. 267-288, Springer-Verlag, 1998). An NTRU cryptosystem is described in detail in Document 2, and therefore no detailed description is given here. In an NTRU cryptosystem, encryption and decryption are performed using polynomial operations by which it is possible to perform operations at higher speed than in the case of RSA (Rivest Shamir Adleman) encryption in which power residue operations are performed modulo a certain natural number and ECC (elliptic-curve cryptography) in which scalar multiplications are performed on points on an elliptic curve. Therefore, an NTRU cryptosystem makes it possible to perform processing at a higher speed by use of software than in the case of existing public key encryption systems.
Thus, an encryption system using an NTRU cryptosystem as public key encryption has an advantage that processing between a transmission apparatus and a receiving apparatus is performed at a higher speed than in the case of an encryption system using an existing public key cryptosystem.
Note that in order to actually perform encryption and decryption using an NTRU cryptosystem, it is necessary to use non-negative integer parameters N, p, q, df, dg, and d (e.g. See Document 2). Presently, concrete values of these parameters are presented (e.g. See Document 5: Joseph H. Silverman, “NTRU Cryptosystems Technical Report #011, Wraps, Gaps, and Lattice Constants”, [online], Jan. 21, 1999, [searched on Apr. 18, 2003]).
In an NTRU cryptosystem, a plain text and a private key are decrypted by third parties using the following methods: undertaking an exhaustive search for the plaintext and private key; and using LLL (Lenstra, Lenstra and Lovasz) algorithm (e.g. See Document 2). The use of parameters presented in Document 5, however, makes the time required for the decryption sufficiently long, as well as making an NTRU cryptosystem a secure method (e.g. See Document 3: Joseph H. Silverman, “NTRU Cryptosystems Technical Report #012, Estimated Breaking Times for NTRU Lattices”, [online], Mar. 9, 1999, [searched on Feb. 18, 2003], Document 4, Joseph H. Silverman, “NTRU Cryptosystems Technical Report #013, Dimension-Reduced Lattices, Zero-Forced Lattices, and the NTRU Public Key Cryptosystem”, [online], Mar. 9, 1999, [searched on Feb. 18, 2003], and Document 5).
However, there is a problem with an NTRU cryptosystem that a decrypted text does not sometimes match the original plain text even when an encrypted text is generated by encrypting the plain text with the public key, and the decrypted text is generated by decrypting such encrypted text with a valid private key (e.g. See Document 2). Such mismatch is called “decryption error”. The occurrence probability of decryption errors depends on parameters for an NTRU cryptosystem (hereinafter referred to also as “NTRU parameters”) (e.g. See Document 5).
Document 2 gives descriptions as to decryption error that, in order to avoid the occurrence of decryption errors, all coefficients in a polynomial (p·r×g+f×m) that is derived by computing the following polynomials must be in the range from −q/2 to q/2: a random polynomial g that is used for generating a public key polynomial h in the NTRU cryptosystem; a random number polynomial r; a plaintext polynomial m; and a private key polynomial f. However, time required for performing decryption when NTRU parameters are chosen in the above manner is unknown, and NTRU parameters that are secure against decryption and that do not cause any decryption errors are still unknown.
As described above, in an NTRU cryptosystem capable of high-speed processing, there is the case where a receiving apparatus cannot properly obtain a plaintext encrypted by a transmission apparatus in the event of a decryption error. Stated another way, an encrypted communication cannot be carried out in a reliable manner between the transmission apparatus and the receiving apparatus.
Needless to say, it is imperative in a cryptosystem that a plain text can be properly conveyed to the destination and that security is assured against decryption by third parties.
However, while the existing technique presents conditions for generating NTRU parameters that do not cause any decryption errors, such conditions are not formulated, which makes it difficult to generate NTRU parameters that do not cause any decryption errors.
Moreover, conditions for generating NTRU parameters that are secure against decryption by third parties and that do not cause any decryption errors are still unknown, and therefore it is not possible to generate such NTRU parameters. This makes it impossible for an encryption apparatus and a decryption apparatus to carry out an encrypted communication in a secure and reliable manner.
The present invention has been conceived in view of the above problems, and it is a first object of the present invention to provide a parameter generation apparatus that generates parameters causing no decryption error for an NTRU cryptosystem, so that an encryption apparatus and a decryption apparatus can carry out an encrypted communication in a secure and reliable manner.
A second object of the present invention is to provide a parameter generation apparatus that generates parameters for an NTRU cryptosystem that are secure against decryption by third parties and that do not cause any decryption errors, so that an encryption apparatus and a decryption apparatus can carry out an encrypted communication in a secure and reliable manner.
Furthermore, a third object of the present invention is to provide an encryption system, an encryption apparatus, and a decryption apparatus by which it is possible for the encryption apparatus and the decryption apparatus to carry out an encrypted communication in a secure and reliable manner by use of parameters generated by the above parameter generation apparatuses.